package SubjectTree.Five;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class SortedArrayToBST {

/**
 * 难度：简单
 * 
 * 108. 将有序数组转换为二叉搜索树
 * 	将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 * 	本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 * 	
 * 示例:
 * 	给定有序数组: [-10,-3,0,5,9],
 * 	一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 * 	      0
 * 	     / \
 * 	   -3   9
 * 	   /   /
 * 	 -10  5
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SortedArrayToBST satbst = new SortedArrayToBST();
		System.out.println(satbst.sortedArrayToBST(new int[] {-10,-3,0,5,9}));
	}
	//递归
	public TreeNode sortedArrayToBST(int[] nums) {
		return traversal(nums, 0, nums.length-1);
    }
	public TreeNode traversal(int[] nums, int left, int right) {
		if(left>right)return null;
		int mid = left + (right - left) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = traversal(nums, left, mid-1);
		root.right = traversal(nums, mid+1, right);
		return root;
	}
	//迭代
	public TreeNode sortedArrayToBST1(int[] nums) {
		if (nums.length == 0) return null;

        TreeNode root = new TreeNode(0);   				// 初始根节点
        Deque<TreeNode> nodeQue = new LinkedList<>();   // 放遍历的节点
        Deque<Integer> leftQue = new LinkedList<>();    // 保存左区间下表
        Deque<Integer> rightQue = new LinkedList<>();   // 保存右区间下表
        nodeQue.push(root);                 // 根节点入队列
        leftQue.push(0);                    // 0为左区间下表初始位置
        rightQue.push(nums.length - 1);     // nums.size() - 1为右区间下表初始位置
		
        while (!nodeQue.isEmpty()) {
            TreeNode curNode = nodeQue.pop();
            int left = leftQue.pop();
            int right = rightQue.pop();
            int mid = left + ((right - left) / 2);

            curNode.val = nums[mid];       	// 将mid对应的元素给中间节点

            if (left <= mid - 1) {          // 处理左区间
                curNode.left = new TreeNode(0);
                nodeQue.push(curNode.left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            if (right >= mid + 1) {         // 处理右区间
                curNode.right = new TreeNode(0);
                nodeQue.push(curNode.right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;
    }
}
